UVa/11675 - Happy friends/11675.2.cpp

   1 using namespace std;
   2 #include <algorithm>
   3 #include <iostream>
   4 #include <iterator>
   5 #include <sstream>
   6 #include <fstream>
   7 #include <cassert>
   8 #include <climits>
   9 #include <cstdlib>
  10 #include <cstring>
  11 #include <string>
  12 #include <cstdio>
  13 #include <vector>
  14 #include <cmath>
  15 #include <queue>
  16 #include <deque>
  17 #include <stack>
  18 #include <list>
  19 #include <map>
  20 #include <set>
  21
  22 template <class T> string toStr(const T &x){ stringstream s; s << x; return s.str(); }
  23 template <class T> int toInt(const T &x){ stringstream s; s << x; int r; s >> r; return r; }
  24
  25 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  26 #define foreach(x, v) for (typeof (v).begin() x = (v).begin(); x != (v).end(); ++x)
  27 #define D(x) cout << #x " = " << (x) << endl
  28
  29 const int MOD = 1000000007;
  30 const int MAXN = 35;
  31
  32 typedef vector< vector<long long> > matrix;
  33
  34 vector<int> g[MAXN];
  35 int day[MAXN];
  36
  37 matrix mul(const matrix &A, const matrix &B){
  38   int p = A.size();
  39   int q = A[0].size();
  40   int r = B[0].size();
  41   matrix C(p, vector<long long>(r, 0));
  42   for (int i=0; i<p; ++i){
  43     for (int j=0; j<r; ++j){
  44       C[i][j] = 0;
  45       for (int k=0; k<q; ++k){
  46         C[i][j] += (A[i][k] * B[k][j]) % MOD;
  47         C[i][j] %= MOD;
  48       }
  49     }
  50   }
  51   return C;
  52 }
  53
  54
  55
  56 matrix exp(const matrix &A, int e){
  57   int n = A.size();
  58   if (e == 0){
  59     matrix C(n, vector<long long>(n, 0));
  60     for (int i=0; i<n; ++i){
  61       C[i][i] = 1;
  62     }
  63     return C;
  64   }
  65
  66   if (e == 1){
  67     return A;
  68   }
  69
  70   matrix B = exp(A, e / 2);
  71   B = mul(B, B);
  72   if (e % 2 == 1){
  73     B = mul(B, A);
  74   }
  75   return B;
  76 }
  77
  78
  79 int main(){
  80   int Casos;
  81   cin >> Casos;
  82   for (int Caso=1; Caso<=Casos; ++Caso){
  83     int n, m, k, d;
  84     if (!(cin >> n >> m >> k >> d)) break;
  85     for (int i=0; i<n; ++i){
  86       g[i].clear();
  87       g[i].push_back(i);
  88       day[i] = -1;
  89     }
  90     while (m--){
  91       int u, v; cin >> u >> v;
  92       g[u].push_back(v), g[v].push_back(u);
  93     }
  94
  95     //find day of sum for each node
  96     queue<int> q;
  97     day[k] = 0;
  98     q.push(k);
  99     while (q.size()){
 100       int u = q.front(); q.pop();
 101       foreach(edge, g[u]){
 102         int v = *edge;
 103         if (day[v] == -1){
 104           day[v] = !day[u];
 105           q.push(v);
 106         }
 107       }
 108     }
 109
 110     matrix odd(n, vector<long long>(n));
 111     matrix even(n, vector<long long>(n));
 112     //find odd/even matrices
 113     for (int j=0; j<n; ++j){
 114       for (int i=0; i<n; ++i){
 115         odd[i][j] = even[i][j] = 0;
 116       }
 117       foreach(edge, g[j]){
 118         int i = *edge;
 119         if (day[j] == 0){
 120           even[i][j] = 1;
 121         }else{
 122           odd[i][j] = 1;
 123         }
 124       }
 125       even[j][j] = odd[j][j] = 1;
 126     }
 127
 128     //D("odd"); For(i, 0, n){ For(j, 0, n) printf("%d ", odd[i][j]); printf("\n"); }
 129
 130     //D("even"); For(i, 0, n){ For(j, 0, n) printf("%d ", even[i][j]); printf("\n"); }
 131
 132     matrix C = mul(odd, even);
 133     C = exp(C, d / 2);
 134     if (d % 2 == 1){
 135       C = mul(C, odd);
 136     }
 137
 138     //D("C"); For(i, 0, n){ For(j, 0, n) printf("%d ", C[i][j]); printf("\n"); }
 139
 140     matrix ans(1, vector<long long>(n));
 141
 142     for (int j=0; j<n; ++j){
 143       ans[0][j] = 0;
 144     }
 145     ans[0][k] = 1;
 146
 147     C = mul(ans, C);
 148
 149     printf("Case %d:", Caso);
 150     for (int j=0; j<n; ++j){
 151       printf(" %d",(int) C[0][j]);
 152     }
 153     printf("\n");
 154   }
 155   return 0;
 156 }